Problem27 二次式素数

問題

オイラーは以下の二次式を考案している:

nの2乗 + n + 41

この式は, nを0から39までの連続する整数としたときに40個の素数を生成する.
しかし, n = 40 のとき 40の2乗 + 40 + 41 = 40(40 + 1) + 41 となり41で割り切れる.
また, n = 41 のときは 41の2乗 + 41 + 41 であり明らかに41で割り切れる.

コンピューターを用いて, 二次式 nの2乗 - 79n + 1601 という式が発見できた.
これは n = 0 から 79 の連続する整数で80個の素数を生成する.
係数の積は, -79 × 1601 で -126479である.

さて, |a| < 1000, |b| < 1000 として以下の二次式を考える
(ここで |a| は絶対値): 例えば |11| = 11 , |-4| = 4である.

nの2乗 + a*n + b

n = 0 から始めて連続する整数で素数を生成したときに
最長の長さとなる上の二次式の, 係数 a, b の積を答えよ.

ソース

using System;

class Program
{
    static void Main()
    {
        Predicate<int> IsSosuu = (pVal) =>
        {
            if (pVal <= 1) return false; //1以下なら素数ではない

            for (int I = 2; I * I <= pVal; I++) {
                if (pVal % I == 0) return false;
            }
            return true;
        };

        int MaxLength = 0;

        for (int a = -999; a <= 999; a++) {
            for (int b = 2; b <= 999; b++) {
                for (int n = 0; n < int.MaxValue; n++) {
                    if (IsSosuu(n * n + n * a + b) == false) break;
                    if (MaxLength < n + 1) {
                        MaxLength = n + 1;
                        Console.WriteLine("a={0},b={1}の時に{2}個の素数を生成し、係数a,bの積={3}",
                            a, b, MaxLength, a * b);
                    }
                }
            }
        }
    }
}

実行結果

省略
a=-61,b=971の時に60個の素数を生成し、係数a,bの積=-59231
a=-61,b=971の時に61個の素数を生成し、係数a,bの積=-59231
a=-61,b=971の時に62個の素数を生成し、係数a,bの積=-59231
a=-61,b=971の時に63個の素数を生成し、係数a,bの積=-59231
a=-61,b=971の時に64個の素数を生成し、係数a,bの積=-59231
a=-61,b=971の時に65個の素数を生成し、係数a,bの積=-59231
a=-61,b=971の時に66個の素数を生成し、係数a,bの積=-59231
a=-61,b=971の時に67個の素数を生成し、係数a,bの積=-59231
a=-61,b=971の時に68個の素数を生成し、係数a,bの積=-59231
a=-61,b=971の時に69個の素数を生成し、係数a,bの積=-59231
a=-61,b=971の時に70個の素数を生成し、係数a,bの積=-59231
a=-61,b=971の時に71個の素数を生成し、係数a,bの積=-59231

解説

nの2乗 + a*n + b
がn=0の時に素数になるのは、bが素数の場合なので、bは2以上となります。

上記をbの定義域とした上で、
aとbの全ての組み合わせで、
nを0からループさせてチェックしてます。